In the newest video compression standard H.264, the video compression performance is greatly enhanced because the advanced designs and tools are adopted. In one aspect thereof, the context-based adaptive binary arithmetic coding (CABAC) is adopted. The CABAC is different from the conventionally adopted variable length coding (VLC) because the arithmetic coding is added. Thus, the transmission speed and storage space may be more effectively due to the higher compression rate. In additions, the arithmetic coding may also compress the binary symbol, which has only two symbols and cannot be compressed by the variable length coding (VLC).
A syntax element (SE) compressed by the CABAC is represented by a variable length bin string. The bin string is composed of one bin or multiple bins. Each bin represents a binary symbol of 0 or 1. The CABAC has to consider the appearance probability of the syntax element symbols, so that the frequently appeared syntax element symbols are used in conjunction with the shorter bin string, and the appearance probability of each bin symbol in the bin string also has to be considered. Then, the arithmetic coding is adopted to achieve the better compression rate.
FIG. 1 (Prior Art) is a schematic illustration showing an original binarization table. In order to convert data with different syntax elements, the CABAC defines different binarization tables, such as an I-Slice MB Type binarization table, a P-Slice MB Type binarization table, a B-Slice MB Type binarization table and the like, according to different syntax elements. In the example of FIG. 1, the B-Slice MB Type binarization table will be illustrated.
The B-Slice MB Type binarization table includes a syntax element symbol (SES) field and a bin string (BS) field. The syntax element symbol field of FIG. 1 includes multiple syntax element symbols SES, such as 0, 1, 2, . . . , 22 and 23. The bin string field includes multiple bin strings BS, such as 0, 100, 101, . . . , 111111 and 111101, respectively corresponding to the syntax element symbols.
FIG. 2 (Prior Art) is a schematic illustration showing a binary search lookup table used by a conventional binary search decoding algorithm. As shown in FIG. 2, the B-Slice MB Type binarization table can be converted into the binary search lookup table through a specific program. The binary search lookup table includes an input field Input and an output field Output. The input field Input includes a node Node and a bin Bin, and the output field Output includes an indicator NodeSE and a flag Flag. Different nodes Node and different bins Bin respectively correspond to different indicators NodeSE and different flags Flag.
When the flag Flag is equal to 1, it represents that the binary search has ended, and the indicator NodeSE is the syntax element symbol corresponding to this bin string. Oppositely, when the flag Flag is equal to 0, it represents that the binary search has not ended yet, and the indicator NodeSE represents the next node Node. Another binary search is performed according to the next node Node and the next bin Bin.
In the de-binarization process, the syntax element symbol corresponding to the received bin string can be found out through the search step.
FIG. 3 (Prior Art) is a schematic illustration showing the binary search lookup table, from which a corresponding syntax element symbol is found out according to a bin string in the prior art. For the sake of simplicity, how the corresponding syntax element symbol 21 is found out will be illustrated by taking the bin string 1111001 of FIG. 3 as an example. The method of finding out the corresponding syntax element symbol 21 according to the bin string 1111001 includes the following search steps.
First, the node Node is initialized to “0”, and the first bin Bin of the bin string is equal to “1”. The first time of binary search is performed according to the node “0” and the bin “1” to find out the flag Flag and the indicator NodeSE corresponding to the node “0” and the bin “1”. At this time, the flag Flag is “0” and the indicator NodeSE is “1”. Because the flag Flag is “0”, it represents that the search has not ended yet. Because the indicator NodeSE is “1”, it represents that the next node is “1”.
Next, the node Node is equal to “1”, and the second bin of the bin string is equal to “1”. The second time of binary search is performed according to the node “1” and the bin “1” to find out the flag Flag and the indicator NodeSE corresponding to the node “1” and the bin “1”. At this time, the flag Flag is “0” and the indicator NodeSE is “2”. Because the flag Flag is “0”, it represents that the search has not ended yet. Because the indicator NodeSE is “2”, it represents that the next node Node is “2”.
Thereafter, the node Node is equal to “2”, and the third bin of the bin string is equal to “1”. The third time of binary search is performed according to the node “2” and the bin “1” to find out the flag Flag and the indicator NodeSE corresponding to the node “2” and the bin “1”. At this time, the flag Flag is “0”, and the indicator NodeSE is “3”. Because the flag Flag is “0”, it represents that the search has not ended yet. Because the indicator NodeSE is “3”, it represents that the next node Node is “3”.
Then, the node Node is equal to “3”, and the fourth bin of the bin string is equal to “1”. The fourth time of binary search is performed according to the node “3” and the bin “1” to find out the flag Flag and the indicator NodeSE corresponding to the node “3” and the bin “1”. At this time, the flag Flag is “0” and the indicator NodeSE is “6”. Because the flag Flag is “0”, it represents that the search has not ended yet. Because the indicator NodeSE is “6”, it represents that the next node Node is “6”.
Next, the node Node is equal to “6” and the fifth bin of the bin string is equal to “1”. The fifth time of binary search is performed according to the node “6” and the bin “1” to find out the flag Flag and the indicator NodeSE corresponding to the node “6” and the bin “1”. At this time, the flag Flag is “0” and the indicator NodeSE is “12”. Because the flag Flag is “0”, it represents that the search has not ended yet. Because the indicator NodeSE is “12”, it represents that the next node Node is “12”.
Thereafter, the node Node is equal to “12”, and the sixth bin of the bin string is equal to “0”. The sixth time of binary search is performed according to the node “12” and the bin “0” to find out the flag Flag and the indicator NodeSE corresponding to the node “12” and the bin “0”. At this time, the flag Flag is “0” and the indicator NodeSE is “22”. Because the flag Flag is “0”, it represents that the search has not ended yet. Because the indicator NodeSE is “22”, it represents that the next node Node is “22”.
Finally, the node Node is equal to “22”, and the seventh bin of the bin string is equal to “1”. The seventh time of binary search is performed according to the node “22” and the bin “1” to find out the flag Flag and the indicator NodeSE corresponding to the node “22” and the bin “1”. At this time, the flag Flag is “1” and the indicator NodeSE is “21”. Because the flag Flag is “1”, it represents that the search has ended. Because the indicator NodeSE is “21”, it represents that the syntax element symbol corresponding to the bin string “1111001” is “21”.